//排序算法
#ifndef __SORT__HPP
#define __SORT__HPP

#include<iostream>
#include<cstring>

namespace NgSiuKei {

#define NormalType unsigned long long

//冒泡排序
template<class TheClass>
void bubbleSort(TheClass *array, NormalType len) {
    if(nullptr == array || 2 > len) {
        return;
    }
    while(len > 0) {
        for(NormalType i=0; i<len-1; ++i) {
            if(array[i]>array[i+1]) {
                std::swap(array[i], array[i+1]);
            }
        }
        len--;
    }
}

//选择排序
template<class TheClass>
void selectionSort(TheClass *array, NormalType len) {
    if(nullptr == array || 2 > len) {
        return;
    }
    NormalType sortedLen = 0;
    NormalType minValIndex;
    TheClass minVal;
    while(sortedLen != len) {
        minVal = array[sortedLen];
        minValIndex = sortedLen;
        for(NormalType i = sortedLen+1; i<len; ++i) {
            if(minVal > array[i]) {
                minVal = array[i];
                minValIndex = i;
            }
        }
        if(minValIndex != sortedLen) {
            std::swap(array[minValIndex], array[sortedLen]);
        }
        ++sortedLen;
    }
}

//插入排序
template<class TheClass>
void insertionSort(TheClass *array, NormalType len) {
    if(nullptr == array || 2 > len) {
        return;
    }
    NormalType sortedLen = 1;
    while(sortedLen != len) {
        for(NormalType i=sortedLen; i>0; --i) {
            if(array[i-1] > array[i]) {
                std::swap(array[i], array[i-1]);
            }
        }
        ++sortedLen;
    }
}

//希尔排序
template<class TheClass>
void shellSort(TheClass *array, NormalType len) {
    if(nullptr == array || 2 > len) {
        return;
    }
    for(NormalType gap=len/2; gap>0; --gap) {
        for(NormalType i=gap; i<len; ++i) {
            for(NormalType j=i-gap; j<len && j>=0 && array[j]>array[i]; j-=gap) {
                std::swap(array[i], array[j]);
            }
        }
    }
}

//归并排序
template<class TheClass>
void mergeSort(TheClass *array, NormalType len) {
    if(nullptr == array || 2 > len) {
        return;
    }
    //将数组拆分，分别进行排序
    TheClass *leftArray = array, *rightArray = array+len/2;
    NormalType leftArrayLen = len/2, rightArrayLen = len-len/2;
    mergeSort(leftArray, leftArrayLen);
    mergeSort(rightArray, rightArrayLen);
    //再合并
    TheClass tempArray[len];
    NormalType l=0, r=0, currentIndex = 0;
    while(l<leftArrayLen && r<rightArrayLen) {
        tempArray[currentIndex++] = ((leftArray[l] < rightArray[r])?(leftArray[l++]):(rightArray[r++]));
    }
    while(l<leftArrayLen) {
        tempArray[currentIndex++] = leftArray[l++];
    }
    while(r<rightArrayLen) {
        tempArray[currentIndex++] = rightArray[r++];
    }
    for(NormalType i=0; i<len; ++i) {
        array[i] = tempArray[i];
    }
}

//快速排序
template<class TheClass>
void quickSort(TheClass *array, NormalType len) {
    if(nullptr == array || 2 > len) {
        return;
    }
    NormalType l=0, r=len-1, mid=l;
    while(l < r && l<len && r<len) {
        if(mid == l) {
            while(array[r]>array[mid]) {--r;}
            if(array[r] < array[mid]) {
                std::swap(array[r], array[mid]);
            }
            mid = r;
            ++l;
        }
        else if(mid == r) {
            while(array[l]<array[mid]) {++l;}
            if(array[l] > array[mid]) {
                std::swap(array[l], array[mid]);
            }
            mid = l;
            --r;
        }
    }
    quickSort(array, mid);
    if(len-mid-1<len) {
        quickSort(array+mid+1, len-mid-1);
    }
}

//桶排序
template<class TheClass>
void bucketSort(TheClass *array, NormalType len) {
    if(nullptr == array || 2 > len) {
        return;
    }
    NormalType i;
    TheClass minVal = array[0], maxVal = array[0];
    for(i=1; i<len; ++i) {
        if(minVal > array[i]) {
            minVal = array[i];
        }
        if(maxVal < array[i]) {
            maxVal = array[i];
        }
    }
    NormalType bucketNum = (maxVal - minVal) / len + 1;
    bool isSimple = bucketNum <= len;//判断用简单分桶还是归约化分桶
    if(!isSimple) {
        bucketNum = len;
    }
    TheClass bucket[bucketNum][len];
    NormalType bucketValNum[bucketNum];
    memset(bucketValNum, 0, sizeof(bucketValNum));
    NormalType bucketIndex;
    for(i=0; i<len; ++i) {
        if(isSimple) {
            bucketIndex = (array[i]-minVal) / len;
        }
        else {
            bucketIndex = ((array[i]-minVal) / (maxVal-minVal)) * len;
        }
        bucket[bucketIndex][bucketValNum[bucketIndex]++] = array[i];
    }
    for(i=0; i<bucketNum; ++i) {
        if(bucketValNum[i] > 1) {
            quickSort(bucket[i], bucketValNum[i]);
        }
    }
    NormalType currentIndex = 0;
    for(i=0; i<bucketNum; ++i) {
        if(bucketValNum[i] > 0) {
            for(NormalType j=0; j<bucketValNum[i]; ++j) {
                array[currentIndex++] = bucket[i][j];
            }
        }
    }
}

//计数排序
template<class TheClass>
void countingSort(TheClass *array, NormalType len) {
    if(nullptr == array || 2 > len) {
        return;
    }
    NormalType i;
    TheClass minVal = array[0], maxVal = array[0];
    for(i=1; i<len; ++i) {
        if(minVal > array[i]) {
            minVal = array[i];
        }
        if(maxVal < array[i]) {
            maxVal = array[i];
        }
    }
    NormalType countingSize = maxVal - minVal + 1;
    NormalType counting[countingSize];
    memset(counting, 0, sizeof(counting));
    for(i=0; i<len; ++i) {
        counting[array[i]-minVal]++;
    }
    NormalType currentIndex = 0;
    for(i=0; i<countingSize; ++i) {
        while(counting[i] > 0) {
            array[currentIndex++] = minVal+i;
            --counting[i];
        }
    }
}

//基数排序（只能用于整数）
template<class TheClass>
void radixSort(TheClass *array, NormalType len) {
    if(nullptr == array || 2 > len) {
        return;
    }
    NormalType i;
    NormalType num[10];
    TheClass tempArray[len];
    TheClass maxVal = array[0];
    for(i=1; i<len; ++i) {
        if(maxVal < array[i]) {
            maxVal = array[i];
        }
    }
    NormalType divisor = 1;
    while(divisor<=maxVal) {
        memset(num, 0, sizeof(num));
        for(i=0; i<len; ++i) {
            tempArray[i] = array[i];
            ++num[(array[i]/divisor)%10];
        }
        for(i=1; i<10; ++i) {
            num[i] += num[i-1];
        }
        for(i=len-1; i>=0 && i<len; --i) {
            array[--num[(tempArray[i]/divisor)%10]] = tempArray[i];
        }
        divisor *= 10;
    }
}

//堆排序
template<class TheClass>
void heapSort(TheClass *array, NormalType len) {
    if(nullptr == array || 2 > len) {
        return;
    }
    NormalType heapLen = len;
    NormalType i;
    while(heapLen > 1) {
        for(i=heapLen-1; i>0; --i) {
            if(array[i] > array[(i-1)/2]) {
                std::swap(array[i], array[(i-1)/2]);
            }
        }
        std::swap(array[0], array[--heapLen]);
    }
}

}

#endif